//
// Created by Incredible on 17/3/21.
//

#ifndef UNIONFIND2_UNIONFIND3_H
#define UNIONFIND2_UNIONFIND3_H
/**
 * 使用size数组进行优化 union
 *
 */

#include <cassert>

namespace UF3 {

    using namespace std;

    class UnionFind {

    private:
        int *parent; //节点的父节点，向上搜索根节点，当parent[i] == i 时 ，该节点为根节点
        int *size; //标识size[i]的树的节点个数（包括该节点）；也不包括该节点，仅标识该根节点树的子节点个数
        int count; //数组大小

    public:

        //初始化并查集
        UnionFind(int count) {
            this->count = count;
            parent = new int[count];
            size = new int[count];

            //将每个节点的根设置为自己，标识其没有根节点，自己就是根
            for (int i = 0; i < count; ++i) {
                parent[i] = i;
                size[i] = 1;    // 1. 1为初始子节点个数（也可以为0 ，仅标识子节点个数）
                // 2. 作用：用该数组保存该节点的子节点个数，在进行合并的时候，将根节点的size少的节点的父节点跟新为size多的节点
            }
        }

        //析构函数(对所有new 开辟的空间进行释放)
        ~UnionFind() {
            delete[] parent;
            delete[] size;
        }

        //查找x的根节点
        int find(int x) {
            //断言 x 是否越界
            assert(x >= 0 && x < count);

            while (x != parent[x]) {
                x = parent[x];
            }
            return x;
        }

        //判断两个节点是否有关联
        bool isConnection(int x, int y) {
            return find(x) == find(y);
        }

        //联合x,y
        void unionElements(int x, int y) {

            //找出需要联合的两个节点的根节点
            int xRoot = find(x);
            int yRoot = find(y);

            //x , y 就是联合的
            if (xRoot == yRoot) {
                return;
            }

            //优化点：
            //将size较少的一方的根节点进行更新，减少树的高度，提高搜索效率
            if (size[xRoot] < size[yRoot]) {

                //将x的根更新为y的根节点
                parent[xRoot] = yRoot;

                //维护size个数，size为原来+新加的
                size[yRoot] += size[xRoot];
            } else {

                //将y的根更新为y的根节点
                parent[yRoot] = xRoot;

                //维护size个数，size为原来+新加的
                size[xRoot] += size[yRoot];
            }


        }


    };
}

#endif //UNIONFIND2_UNIONFIND3_H
